import java.util.*;

/**
 * description: <a href="https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4">牛客网-购物单</a>
 *
 * @author <a href="zhaoyingling12@163.com">simon zhao</a>
 * @since 2023/3/27
 */
public class ShoppingList {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 用户的金额
        int N = in.nextInt();
        // 可购买件数
        int m = in.nextInt();
        // 初始化数据
        List<Good> goods = initData(in, N, m);
        // dp[i][j] 表示在购买第i件物品，且开销为j的基础上的最大满意度
        int[][] dp = new int[goods.size() + 1][N + 1];
        for (int i = 1; i <= goods.size(); i++) {
            Good good = goods.get(i - 1);
            for (int j = 0; j <= N; j++) {
                // 不买的情况
                dp[i][j] = dp[i - 1][j];
                // 买主件
                if (j >= good.price) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - good.price] + good.value);
                }
                // 买主件 + 配件1
                if (good.good1 != null && j >= good.price + good.good1.price) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - good.price - good.good1.price] + good.value + good.good1.value);
                }
                // 买主件 + 配件2
                if (good.good2 != null && j >= good.price + good.good2.price) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - good.price - good.good2.price] + good.value + good.good2.value);
                }
                // 买主件 + 配件1 + 配件2
                if (good.good1 != null && good.good2 != null && j >= good.price + good.good1.price + good.good2.price) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - good.price - good.good1.price - good.good2.price] + good.value + good.good1.value + good.good2.value);
                }
            }
        }
        System.out.println(dp[goods.size()][N]);
    }

    private static List<Good> initData(Scanner in, int N, int m) {
        Map<Integer, Good> map = new HashMap<>();
        // key 配件所属主件
        Map<Integer, List<Good>> goodTmpMap = new HashMap<>();
        for (int id = 1; id <= m; id++) {
            int price = in.nextInt();
            int importance = in.nextInt();
            int belong = in.nextInt();
            // 先过滤一下 价格大于N 无法购买
            if (price > N) {
                continue;
            }
            if (belong == 0) { //主件添加到map中
                map.put(id, new Good(price, importance));
            } else {
                //附件添加到主件的属性中
                if (map.get(belong) == null) {
                    List<Good> goods = goodTmpMap.getOrDefault(belong, new ArrayList<>());
                    goods.add(new Good(price, importance));
                    goodTmpMap.put(belong, goods);
                } else {
                    map.get(belong).addGood(new Good(price, importance));
                }
            }
        }
        if (!goodTmpMap.isEmpty()) {
            for (Integer key : goodTmpMap.keySet()) {
                List<Good> goods = goodTmpMap.get(key);
                // 说明对应的主件已经被淘汰[价格过高] 附件也无需购买
                if (goods == null) {
                    continue;
                }
                for (Good good : goods) {
                    map.get(key).addGood(good);
                }
            }
        }
        // 一旦为每个附件配置好主件以后 配件的id就没有任何用处了
        return new ArrayList<>(map.values());
    }


    static class Good {
        int price;
        int value;
        Good good1;
        Good good2;

        public Good(int price, int importance) {
            this.price = price;
            this.value = price * importance;
        }

        public void addGood(Good good) { //为主件添加附件
            if (good1 == null) {
                good1 = good;
            } else if (good2 == null) {
                good2 = good;
            }
        }
    }
}
